package com.heima.leetcode.datastructure.linkedlist;

/**
 * <h2>判断回文链表</h2>
 */
public class IsPalindrome {

    /**
     * <h3>方法一</h3>
     * @param head 链表的头节点
     * @return 是否是回文链表
     */

    /*
    * 1、找到链表的中间节点
    * 2、反转中间节点以后的链表
    * 3、比较是否和前半部分的链表一致
    */

    public static boolean isPalindromeList1(ListNode head){
        if (head == null){
            return false;
        }
        // 1、找到链表的中间节点
        ListNode middle = middle(head);
        // 2、反转中间节点以后的链表
        ListNode newHead = reverse(middle);
        // 3、比较是否和前半部分的链表一致
        while (newHead != null){
            if (head.val != newHead.val){
                return false;
            }
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }

    private static ListNode middle(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    private static ListNode reverse(ListNode oldHead){
        ListNode newHead = oldHead;
        while (oldHead != null && oldHead.next != null){
            ListNode next = oldHead.next;
            oldHead.next = next.next;
            next.next = newHead;
            newHead = next;
        }
        return newHead;
    }

    /**
     * <h3>方法二</h3>
     * @param head 链表头节点
     * @return 是否是回文链表
     */

    /*
    * 1、找中间节点的同时让前半链表反转
    * 2、让前半链表和后半链表进行一一比较
    */

    public static boolean isPalindromeList2(ListNode head){
            // 找到中间节点的同时让前半链表反转
        ListNode p1 = head;
        ListNode p2 = head;
        ListNode oldHead = head;
        ListNode newHead = null;
        while (p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
            // 前半链表反转
            oldHead.next = newHead;
            newHead = oldHead;
            oldHead = p1;
        }
        // 让前半链表和后半链表进行一一比较
        // 判断是否是奇数个节点
        if (p2 != null){
            p1 = p1.next;
        }
        // 一一比较
        while (newHead != null){
            if (newHead.val != p1.val){
                return false;
            }
            newHead = newHead.next;
            p1 = p1.next;
        }
        return true;
    }
}
